//
// Created by yangchao on 2022/4/27.
// 34. 在排序数组中查找元素的第一个和最后一个位置:
// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
//
#include <vector>
using namespace std;

class SearchRange {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2,-1);
        bool isFirst = false;
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            //先找到任意一个target，然后再从两端依次确认起始和结束索引
            if (nums[mid] == target) {
                for (int i = left; i <= right ; ++i) {
                    if (nums[i] == target) {
                        if (!isFirst) {
                            res[0] = i;
                            isFirst = true;
                            res[1] = i;
                        } else {
                            res[1] = i;
                        }
                    }
                }
                return res;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
};


